11338 - Minefield/11338.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <queue>
   4 #include <map>
   5 #include <cmath>
   6 #include <sstream>
   7 #include <functional>
   8
   9 using namespace std;
  10
  11 const double infinity = 1E20;
  12
  13 struct point{
  14   double x, y;
  15   point(double X, double Y){ x = X; y = Y;}
  16 };
  17
  18 map< point, double > dist;
  19
  20 bool operator ==(const point &a, const point &b){ return (a.x == b.x && a.y == b.y);}
  21 bool operator !=(const point &a, const point &b){ return !(a == b);}
  22 bool operator <(const point &a, const point &b){ return (a.x < b.x || (a.x == b.x && a.y < b.y));}
  23 //bool operator <(point a, point b){ return (a.dist > b.dist);}
  24 double distancia(point a, point b){return hypot(a.y-b.y, a.x-b.x);}
  25
  26
  27
  28 bool heapCmp(const point &a,const point &b){
  29   return (dist[a] > dist[b]);
  30 }
  31
  32
  33 struct heapCompare : public binary_function<point, point, bool>
  34 {
  35   bool operator()(const point &x, const point &y) const
  36   { return dist[x] > dist[y]; }
  37 };
  38
  39
  40 struct grafo{
  41   //contiene todos los nodos sueltos
  42   vector<point> nodos;
  43   //contiene un vector con todos los vecinos para el punto point
  44   map< point, vector<point> > vecinos;
  45
  46   void insert(point a){
  47     if (find(nodos.begin(), nodos.end(), a) != nodos.end()) return; //Ya insertamos este nodo
  48     nodos.push_back(a);
  49     for (int i=0; i<nodos.size(); ++i){
  50       //Insertarlo como vecino en los nodos diferentes a el mismo
  51       if (nodos[i] != a){
  52         vector<point> adj = vecinos[nodos[i]];
  53         //Asegurarse de no insertar un vecino repetido
  54         if (find(adj.begin(), adj.end(), a) == adj.end()){
  55           if (distancia(a, nodos[i]) < 1.5){
  56             //printf("Insertando (%f,%f) como vecino de (%f,%f).\n", a.x, a.y, nodos[i].x, nodos[i].y);
  57             vecinos[nodos[i]].push_back(a);
  58             vecinos[a].push_back(nodos[i]);
  59           }
  60         }
  61       }
  62     }
  63   }
  64
  65   void initialize(){
  66     dist.clear();
  67     for (int i=0; i<nodos.size(); ++i){
  68       dist[nodos[i]] = infinity;
  69       if (nodos[i].x == 0.00 && nodos[i].y == 0.00){
  70         dist[nodos[i]] = 0.00;
  71       }
  72     }
  73   }
  74
  75   /*void relax(point u, point v){
  76     if (dist[v] > dist[u] + distancia(u, v)){
  77       dist[v] = dist[u] + distancia(u, v);
  78     }
  79     }*/
  80
  81   void dijkstra(const double &maxPath, const point &finalPoint){
  82     initialize();
  83
  84     //priority_queue<point, vector<point>, heapCompare > q(nodos.begin(), nodos.end());
  85     priority_queue<point, vector<point>, heapCompare > q;
  86     q.push(point(0.0, 0.0));
  87     //vector<point> q(nodos.begin(), nodos.end());
  88     //make_heap(q.begin(), q.end(), heapCmp);
  89     while (!q.empty()){
  90       //point u = q.front();
  91       //pop_heap(q.begin(), q.end(), heapCmp); q.pop_back();
  92       point u = q.top();
  93       q.pop();
  94       //printf("Saque (%f,%f) cuya distancia es %f\n", u.x, u.y, dist[u]);
  95       if (distancia(point(0.00, 0.00), u) + distancia(u, finalPoint) <= maxPath){
  96         for (int i=0; i<vecinos[u].size(); ++i){
  97           point v = vecinos[u][i];
  98           //printf("  Comparando (%f,%f) con (%f,%f) que estan a %f\n", u.x, u.y, v.x, v.y, distancia(u,v));
  99           //printf(" dist[u] es %f, dist[v] es %f\n", dist[u], dist[v]);
 100           if (dist[vecinos[u][i]] > (dist[u] + distancia(u,v))){
 101             //printf("  Actualizando la distancia de v = (%f,%f)\n", v.x, v.y);
 102             dist[vecinos[u][i]] = dist[u] + distancia(u, v);
 103             //printf("  Nueva distancia de v: %f\n", dist[v]);
 104             q.push(v);
 105           }
 106         }
 107       }
 108       //make_heap(q.begin(), q.end(), heapCmp);
 109     }
 110   }
 111
 112 };
 113
 114
 115
 116 int main(){
 117   while (true){
 118
 119     string s;
 120     for (s = ""; s == ""; getline(cin, s));
 121     if (s == "*") break;
 122
 123
 124     grafo g;
 125
 126     stringstream line;
 127     line << s;
 128
 129     int w,h;
 130     line >> w >> h;
 131     g.insert(point((double)w, (double)h));
 132     g.insert(point(0.00, 0.00));
 133     int noPuntos;
 134     cin >> noPuntos;
 135     for (int i=0; i<noPuntos; ++i){
 136       double x,y;
 137       cin >> x >> y;
 138       g.insert(point(x,y));
 139     }
 140
 141     cout << "Termine de insertar todos los nodos.\n";
 142
 143     double maximoCamino;
 144     cin >> maximoCamino;
 145
 146     /*printf("Voy a imprimir el grafo de %d nodos:\n", g.nodos.size());
 147     for (int i=0; i<g.nodos.size(); ++i){
 148       printf("Estos son los vecinos de (%f,%f):\n", g.nodos[i].x, g.nodos[i].y);
 149       for (int j=0; j<g.vecinos[g.nodos[i]].size(); ++j){
 150         printf("  (%f,%f)\n", g.vecinos[g.nodos[i]][j].x, g.vecinos[g.nodos[i]][j].y);
 151       }
 152       }*/
 153
 154     g.dijkstra(maximoCamino, point((double)w, (double)h));
 155     //printf("La distancia minima hasta (%d,%d) es %f.\n", w,h,dist[point((double)w, (double)h)]);
 156     if (dist[point((double)w, (double)h)] < maximoCamino){
 157       printf("I am lucky!\n");
 158     }else{
 159       printf("Boom!\n");
 160     }
 161
 162   }
 163   return 0;
 164 }